package com.cqs.leetcode;

/**
 * Author:li
 * <p>
 * create date: 18-5-29 12:32
 */
public class InsertionSortList147 {

    //插入排序
    //38 ms
    public ListNode insertionSortList(ListNode head) {
        if (head == null || head.next == null) return head;

        ListNode node = head.next;
        ListNode pre = head;
        ListNode next = node.next;

        //需要考虑一些边界情况
        do {
            //先从链表中删除节点node
            pre.next = next;
            node.next = null;

            ListNode p = head, pp = null;
            while (p != next && p.val < node.val) {
                pp = p;
                p = p.next;
            }
            //
            node.next = p;
            if (pp == null) {
                head = node;
            } else {
                pp.next = node;
            }
            //更新pre节点
            if (node.next == next) {
                pre = node;
            }
            node = next;
            if (next != null) {
                next = next.next;
            }
        } while (node != null);
        return head;
    }


    //leetcode 4ms---- 归并排序
    class Solution {
        public ListNode insertionSortList(ListNode head) {
            if (head == null || head.next == null) return head;

            ListNode prev = null, slow = head, fast = head;

            // find the middle node 1->2->3->4->5->6
            //                            ^  ^     ^
            //                            p  s     f
            while (fast != null && fast.next != null) {
                prev = slow;
                slow = slow.next;
                fast = fast.next.next;
            }
            prev.next = null; // divide

            ListNode left = insertionSortList(head);
            ListNode right = insertionSortList(slow);

            return merge(left, right);
        }

        private ListNode merge(ListNode left, ListNode right) {
            if (left == null) return right;
            if (right == null) return left;

            if (right.val < left.val) {
                right.next = merge(right.next, left);
                return right;
            } else {
                left.next = merge(left.next, right);
                return left;
            }
        }
    }
}

